package com.zyblue.fastim.common.mytest.algorithm.array;

/**
 * @author will
 * @date 2022/2/10 19:11
 * 找出数组中重复的数字。
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 *
 * 示例 1：
 *
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 *
 * 要求时间复杂度 O(N) 空间复杂度O(1)
 */
public class FindDuplicateKeyV2 {

    public int findRepeatNumber(int[] nums) {
        //原地交换算法
        // [(2), 3, 1, 0, 2, 5, 3]
        // [(1), 3, 2, 0, 2, 5, 3]
        // [(3), 1, 2, 0, 2, 5, 3]
        // [(0), 1, 2, 3, 2, 5, 3]
        // [0, (1), 2, 3, 2, 5, 3]  [0, 1, (2), 3, 2, 5, 3]  [0, 1, 2, (3), 2, 5, 3]
        // [0, 1, 2, 3, (2), 5, 3] index为4的位置2元素，在index为2下元素相同
        return 0;
    }
}
